package leetcode.editor.cn;

import java.lang.reflect.Array;

/**
 * @id: 526
 * @title: 优美的排列
 */
 
//假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，
//我们就称这个数组为一个优美的排列。条件： 
//
// 
// 第 i 位的数字能被 i 整除 
// i 能被第 i 位上的数字整除 
// 
//
// 现在给定一个整数 N，请问可以构造多少个优美的排列？ 
//
// 示例1: 
//
// 
//输入: 2
//输出: 2
//解释: 
//
//第 1 个优美的排列是 [1, 2]:
//  第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
//  第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除
//
//第 2 个优美的排列是 [2, 1]:
//  第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
//  第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除
// 
//
// 说明: 
//
// 
// N 是一个正整数，并且不会超过15。 
// 
// Related Topics 位运算 数组 动态规划 回溯 状态压缩 
// 👍 172 👎 0

public class P526BeautifulArrangement {
    public static void main(String[] args) {
        Solution solution = new P526BeautifulArrangement().new Solution();
        // todo
        int result = solution.countArrangement(4);
        System.out.println(result);
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countArrangement(int n) {
        int mask = 1 << n;
        int[][] barr = new int[n+1][mask];
        barr[0][0] = 1;
        if (n == 1) {
            return 1;
        }
        // i 为下标
        for (int i = 1 ; i <= n ; i++) {
            // state代表值是否被使用
            for (int state = 0 ; state < mask ; state++) {
                // 代表数
                for (int j = 1 ; j <= n ; j++) {
                    // 当前数值被使用
                    if (((state >> (j-1)) & 1) == 0 ) continue;
                    // 如果不满足条件
                    if (i%j != 0 && j%i != 0) {
                        continue;
                    }
                    // 找到使用了的值的位置
                    int bar = state & (~(1 << (j - 1)));
                    barr[i][state] += barr[i-1][bar];
                }
//                System.out.print(barr[i][state] + "  ");
            }
//            System.out.println();
        }
        return barr[n][mask-1];
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}